Search for: All records

Recently, a plethora of works have proposed inference-time algorithms (e.g. best-of-n), which incorporate verifiers to assist the generation process. Their quality-efficiency trade-offs have been empirically benchmarked on a variety of constrained generation tasks, but the algorithmic design landscape is still largely poorly understood. In this paper, we develop a mathematical framework for reasoning about constrained generation using a pre-trained language model generator oracle and a process verifier--which can decide whether a prefix can be extended to a string which satisfies the constraints of choice. We show that even in very simple settings, access to a verifier can render an intractable problem (information-theoretically or computationally) to a tractable one. In fact, we show even simple algorithms, like tokenwise rejection sampling, can enjoy significant benefits from access to a verifier. Empirically, we show that a natural modification of tokenwise rejection sampling, in which the sampler is allowed to "backtrack" (i.e., erase the final few generated tokens) has robust and substantive benefits over natural baselines (e.g. (blockwise) rejection sampling, nucleus sampling)--both in terms of computational efficiency, accuracy and diversity. 

Abstract Climate models generally overestimate observed Southern Ocean surface warming trends over the past three decades. This discrepancy could be due to biased surface freshwater fluxes in climate models, which underestimate observed precipitation increases and do not account for Antarctic Ice Sheet and shelf mass loss. Though past modeling experiments show surface cooling in response to freshwater perturbations, sea surface temperature (SST) responses vary widely across models. To address these ambiguities, we compute linear SST response functions for standardized freshwater flux increases across a subset of CMIP6 models. For 1990–2021, underestimated freshwater fluxes can explain up to 60% of the model‐observation SST trend difference. The response functions reveal that Southern Ocean SST trends are more sensitive to freshwater fluxes concentrated along the Antarctic margin versus more spatially distributed fluxes. Our results quantify, for the first time, the impact of missing freshwater forcing on Southern Ocean SST trends across a multi‐model ensemble. 

We analyze inexact Riemannian gradient descent (RGD) where Riemannian gradients and retractions are inexactly (and cheaply) computed. Our focus is on understanding when inexact RGD converges and what is the complexity in the general nonconvex and constrained setting. We answer these questions in a general framework of tangential Block Majorization-Minimization (tBMM). We establish that tBMM converges to an 𝜖-stationary point within 𝑂(𝜖−2) iterations. Under a mild assumption, the results still hold when the subproblem is solved inexactly in each iteration provided the total optimality gap is bounded. Our general analysis applies to a wide range of classical algorithms with Riemannian constraints including inexact RGD and proximal gradient method on Stiefel manifolds. We numerically validate that tBMM shows improved performance over existing methods when applied to various problems, including nonnegative tensor decomposition with Riemannian constraints, regularized nonnegative matrix factorization, and low-rank matrix recovery problems. 

We analyze inexact Riemannian gradient descent (RGD) where Riemannian gradients and retractions are inexactly (and cheaply) computed. Our focus is on understanding when inexact RGD converges and what is the complexity in the general nonconvex and constrained setting. We answer these questions in a general framework of tangential Block Majorization-Minimization (tBMM). We establish that tBMM converges to an $$\epsilon$$-stationary point within $$O(\epsilon^{-2})$$ iterations. Under a mild assumption, the results still hold when the subproblem is solved inexactly in each iteration provided the total optimality gap is bounded. Our general analysis applies to a wide range of classical algorithms with Riemannian constraints including inexact RGD and proximal gradient method on Stiefel manifolds. We numerically validate that tBMM shows improved performance over existing methods when applied to various problems, including nonnegative tensor decomposition with Riemannian constraints, regularized nonnegative matrix factorization, and low-rank matrix recovery problems. 

Abstract We investigate the role of ocean heat transport (OHT) in driving the decadal variability of the Arctic climate by analyzing the pre‐industrial control simulation of a high‐resolution climate model. While the OHT variability at 65°N is greater in the Atlantic, we find that the decadal variability of Arctic‐wide surface temperature and sea ice area is much better correlated with Bering Strait OHT than Atlantic OHT. In particular, decadal Bering Strait OHT variability causes significant changes in local sea ice cover and air‐sea heat fluxes, which are amplified by shortwave feedbacks. These heat flux anomalies are regionally balanced by longwave radiation at the top of the atmosphere, without compensation by atmospheric heat transport (Bjerknes compensation). The sensitivity of the Arctic to changes in OHT may thus rely on an accurate representation of the heat transport through the Bering Strait, which is difficult to resolve in coarse‐resolution ocean models. 

Autoregressive language models are the currently dominant paradigm for text generation, but they have some fundamental limitations that cannot be remedied by scale—for example inherently sequential and unidirectional generation. While alternate classes of models have been explored, we have limited mathematical understanding of their fundamental power and limitations. In this paper we focus on Generative Masked Language Models (GMLMs), a non-autoregressive paradigm in which we train a model to fit conditional probabilities of the data distribution via masking, which are subsequently used as inputs to a Markov Chain to draw samples from the model. These models empirically strike a promising speed-quality tradeoff as each step can be typically parallelized by decoding the entire sequence in parallel. We develop a mathematical framework for analyzing and improving such models which sheds light on questions of sample complexity and inference speed and quality. Empirically, we adapt the T5 model for iteratively-refined parallel decoding, achieving 2-3x speedup in machine translation with minimal sacrifice in quality compared with autoregressive models. We run careful ablation experiments to give recommendations on key design choices, and make fine-grained observations on the common error modes in connection with our theory. Our mathematical analyses and empirical observations characterize both potentials and limitations of this approach, and can be applied to future works on improving understanding and performance of GMLMs. 

Social interactions unfold within networks of relationships. How do beliefs about others’ social ties shape—and how are they shaped by—expectations about how others will behave? Here, participants joined a fictive online game-playing community and interacted with its purported members, who varied in terms of their trustworthiness and apparent relationships with one another. Participants were less trusting of partners with untrustworthy friends, even after they consistently showed themselves to be trustworthy, and were less willing to engage with them in the future. To test whether people not only expect friends to behave similarly but also expect those who behave similarly to be friends, an incidental memory test was given. Participants were exceptionally likely to falsely remember similarly behaving partners as friends. Thus, people expect friendship to predict similar behavior and vice versa. These results suggest that knowledge of social networks and others’ behavioral tendencies reciprocally interact to shape social thought and behavior.